home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / jovept2.arc / RE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1985-05-30  |  14.9 KB  |  760 lines
  1. /* re.c */
  2.  
  3. /* JOVE/MSDOS. K. Mitchum 1/85 */
  4. /* Modifications for personal use only. */
  5. /* original code J. Payne LSRHS 5/83 */
  6. /* Ken Mitchum */
  7. /* University of Pittsburgh */
  8. /* Decision Systems Laboratory */
  9.  
  10. /*
  11.    Jonathan Payne at Lincoln-Sudbury Regional High School 5-25-83
  12.  
  13.    jove_re.c
  14.  
  15.    Much of this code was taken from /usr/src/cmd/ed.c.  It has been
  16.    modified a lot and features have been added, but the general algorithm
  17.    is the same. */
  18.  
  19. #include "jove.h"
  20.  
  21.  
  22. #define    CBRA        1    /* \( */
  23. #define    CCHR        2    /* Normal comparisn */
  24. #define    CDOT        4    /* Matches any character */
  25. #define    CCL        6    /* [0-9] matches 0123456789 */
  26. #define    NCCL        8    /* a '^' inside a [...] */
  27. #define    CDOL        10    /* Match at end of the line */
  28. #define    CEOF        12    /* End of line */
  29. #define    CKET        14    /* \) */
  30. #define    CBACK        16    /* \1 \2 \3 ... */
  31. #define CIRC        18    /* At beginning of line */
  32. #define CWORD        20    /* A word character    \w */
  33. #define CNWORD        22    /* Not a word character \W */
  34. #define CBOUND        24    /* At a word boundary   \b */
  35. #define CNBOUND        25    /* Not at a word boundary \B */
  36. #define    STAR    01
  37. #define SEARCHSIZE 100
  38. #define EOL    -1
  39. #define    NBRA    5
  40. #define NALTS    10
  41. #define CharCom(a, b) (IsFlagSet(globflags, CASEIND) ? \
  42.     (Upperc(a) == Upperc(b)) : (a == b))
  43.  
  44. char searchbuf[SEARCHSIZE];
  45.  
  46. static char *loc1,        /* Beginning of found search */
  47.     *loc2,        /* End of found search */
  48.     *locs;        /* Where to start comparison */
  49.  
  50.  
  51. static char *braslist[NBRA],
  52.     *braelist[NBRA],
  53.     *alternates[NALTS];
  54. static int nbra;
  55. static char unmatched[] = "unmatched parens?";
  56. static char toolong[] = "too long";
  57. static char syntax[] = "syntax?";
  58. static char *reptr,        /* Pointer to the expression to search for */
  59.     rhsbuf[LBSIZE/2],
  60.     expbuf[ESIZE+4];
  61. static int dir,
  62.     REpeekc;
  63.  
  64.  
  65. REerror(str)
  66. char    *str;
  67. {
  68.     complain("RE error: %s", str);
  69. }
  70.  
  71. nextc()
  72. {
  73.     int    c;
  74.  
  75.     if (c = REpeekc)
  76.         REpeekc = 0;
  77.     else if (*reptr == 0)
  78.         c = EOL;
  79.     else
  80.         c = *reptr++;
  81.     return c;
  82. }
  83.  
  84. QRepSearch()
  85. {
  86.     replace(1);
  87. }
  88.  
  89. RepSearch()
  90. {
  91.     replace(0);
  92. }
  93.  
  94. /* Prompt for search and replacement string and do the substitution.
  95.    The point is saved and restored at the end. */
  96.  
  97. replace(query)
  98. {
  99.     MARK    *save = MakeMark(curline, curchar);
  100.  
  101.     REpeekc = 0;
  102.     reptr = ask(searchbuf[0] ? searchbuf : (char *) 0,
  103.             ": %sreplace-search ", query ? "query-" : "");
  104.     strcpy(searchbuf, reptr);
  105.     compile(EOL, IsFlagSet(globflags, MAGIC));
  106.             /* Compile search string complaining
  107.              * about errors before asking for 
  108.              * the replacement string.
  109.              */
  110.     reptr = ask("", "Replace \"%s\" with: ", searchbuf);
  111.     compsub(EOL);
  112.         /* Compile replacement string */
  113.     substitute(query);
  114.     ToMark(save);
  115.     DelMark(save);
  116. }
  117.  
  118. /* Return a buffer location of where the search string in searchbuf is.
  119.    NOTE: this procedure used to munge all over linebuf, but doesn't
  120.    anymore (It uses genbuf instead!). */
  121.  
  122. BUFLOC *
  123. dosearch(str, direction, magic)
  124. char    *str;
  125. {
  126.     static BUFLOC    ret;
  127.     LINE    *a1;
  128.     int    fromchar;
  129.  
  130.     dir = direction;
  131.     reptr = str;        /* Read from this string */
  132.     REpeekc = 0;
  133.     compile(EOL, magic);
  134.  
  135.     a1 = curline;
  136.     fromchar = curchar;
  137.     if (dir < 0)
  138.         fromchar--;
  139.     
  140.     if (fromchar >= strlen(linebuf) && dir > 0)
  141.         a1 = a1->l_next, fromchar = 0;
  142.     else if (fromchar < 0 && dir < 0)
  143.         a1 = a1->l_prev, fromchar = a1 ? length(a1) : 0;
  144.     for (;;) {
  145.         if (a1 == 0)
  146.             break;
  147.         if (execute(fromchar, a1))
  148.             break;
  149.         a1 = dir > 0 ? a1->l_next : a1->l_prev;
  150.         if (dir < 0 && !a1)    /* don't do the length if == 0 */
  151.             break;
  152.         fromchar = dir > 0 ? 0 : length(a1);
  153.     }
  154.  
  155.     if (a1) {
  156.         ret.p_line = a1;
  157.         ret.p_char = dir > 0 ? loc2 - genbuf : loc1 - genbuf;
  158.         return &ret;
  159.     }
  160.     return 0;
  161. }
  162.  
  163. setsearch(str)
  164. char    *str;
  165. {
  166.     strcpy(searchbuf, str);
  167. }
  168.  
  169. ForSearch()
  170. {
  171.     search(1);
  172. }
  173.  
  174. RevSearch()
  175. {
  176.     search(0);
  177. }
  178.  
  179. /* Prompts for a search string.  Complains if the string cannot be found.
  180.    Searches don't wrap line in ed/vi */
  181.  
  182. search(forward)
  183. {
  184.     BUFLOC    *newdot;
  185.  
  186.     dir = forward ? 1 : -1;
  187.     reptr = ask(searchbuf[0] ? searchbuf : (char *) 0, FuncName());
  188.  
  189.     setsearch(reptr);
  190.     message(searchbuf);
  191.     UpdateMesg();        /* Only message not whole screen! */
  192.     newdot = dosearch(searchbuf, dir, IsFlagSet(globflags, MAGIC));
  193.     if (newdot == 0)
  194.         complain("Search for \"%s\" failed", searchbuf);
  195.     SetMark();
  196.     SetDot(newdot);
  197. }
  198.  
  199. /* Perform the substitution.  Both the replacement and search strings have 
  200.    been compiled already.  This knows how to deal with query replace. */
  201.  
  202. substitute(query)
  203. {
  204.     LINE    *lp;
  205.     int    numdone = 0,
  206.         fromchar = curchar,
  207.         stop = 0;
  208.  
  209.     dir = 1;    /* Always going forward */
  210.     for (lp = curline; !stop && lp; lp = lp->l_next, fromchar = 0) {
  211.         while (!stop && execute(fromchar, lp)) {
  212.             DotTo(lp, loc2 - genbuf);
  213.             fromchar = curchar;
  214.             if (query) {
  215.                  message("Replace (Type '?' for help)? ");
  216. reswitch:
  217.                 switch (Upperc((*Gtchar)())) {
  218.                 case '.':
  219.                     stop++;    /* Stop after this */
  220.  
  221.                 case ' ':
  222.                     break;    /* Do the replace */
  223.  
  224.                 case '\177':    /* Skip this one */
  225.                     continue;
  226.  
  227.                 case 'R':    /* Allow user to move around */
  228.                     {
  229.                     BUFFER    *oldbuf = curbuf;
  230.                         MARK    *m;
  231.                         char    pushexp[ESIZE + 4];
  232.  
  233.                         fromchar = loc1 - genbuf;
  234.                         m = MakeMark(curline, fromchar);
  235.                         curchar = loc2 - genbuf;
  236.                     message("Recursive edit ...");
  237.                         copynchar(pushexp, expbuf, ESIZE + 4);
  238.                     Recurse();
  239.                         copynchar(expbuf, pushexp, ESIZE + 4);
  240.                     SetBuf(oldbuf);
  241.                         ToMark(m);
  242.                         DelMark(m);
  243.                         fromchar = curchar;
  244.                         lp = curline;
  245.                     continue;
  246.                     }
  247.  
  248.                 case 'P':    /* Replace all */
  249.                     query = 0;    /* Replace all */
  250.                     break;
  251.  
  252.                 case '\n':    /* Stop this replace search */
  253.                 case '\r':
  254.                     goto done;
  255.  
  256.                 default:
  257.                     rbell();
  258.                 case '?':
  259. message("<SP> => yes, <DEL> => no, <CR> => stop, 'r' => recursive edit, 'p' => proceed");
  260.                     goto reswitch;
  261.                 }
  262.  
  263.             }
  264.             dosub(linebuf);        /* Do the substitution */
  265.             numdone++;
  266.             SetModified(curbuf);
  267.             fromchar = curchar = loc2 - genbuf;
  268.             exp = 1;
  269.             makedirty(curline);
  270.             if (query) {
  271.                 message(mesgbuf);    /* No blinking ... */
  272.                 redisplay();    /* Show the change */
  273.             }
  274.             if (linebuf[fromchar] == 0)
  275.                 break;
  276.         }
  277.     }
  278. done:
  279.     if (numdone == 0)
  280.         complain("None found");
  281.     s_mess("%d substitution%s", numdone, numdone ? "s" : "");
  282. }
  283.  
  284. /* Compile the substitution string */
  285.  
  286. compsub(seof)
  287. {
  288.     register int    c;
  289.     register char    *p;
  290.  
  291.     p = rhsbuf;
  292.     for (;;) {
  293.         c = nextc();
  294.         if (c == '\\')
  295.             c = nextc() | 0200;
  296.         if (c == seof)
  297.             break;
  298.         *p++ = c;
  299.         if (p >= &rhsbuf[LBSIZE/2])
  300.             REerror(toolong);
  301.     }
  302.     *p++ = 0;
  303. }
  304.  
  305. dosub(base)
  306. char    *base;
  307. {
  308.     register char    *lp,
  309.             *sp,
  310.             *rp;
  311.     int    c;
  312.  
  313.     lp = genbuf;
  314.     sp = base;
  315.     rp = rhsbuf;
  316.     while (lp < loc1)
  317.         *sp++ = *lp++;
  318.     while (c = *rp++ & 0377) {
  319.         if (c == '&') {
  320.             sp = place(LBSIZE, base, sp, loc1, loc2);
  321.             continue;
  322.         } else if (c & 0200 && (c &= 0177) >= '1' && c < nbra + '1') {
  323.             sp = place(LBSIZE, base, sp, braslist[c - '1'], braelist[c - '1']);
  324.             continue;
  325.         }
  326.         *sp++ = c & 0177;
  327.         if (sp >= &base[LBSIZE])
  328.             REerror(toolong);
  329.     }
  330.     lp = loc2;
  331.     loc2 = genbuf + max(1, sp - base);
  332.             /* At least one character forward after the replace
  333.                to prevent infinite number of replacements in the
  334.                same place, e.g. replace "^" with "" */
  335.     
  336.     while (*sp++ = *lp++)
  337.         if (sp >= &base[LBSIZE])
  338.             len_error(ERROR);
  339. }
  340.  
  341. char *
  342. place(size, base, sp, l1, l2)
  343. char    *base;
  344. register char    *sp,
  345.         *l1,
  346.         *l2;
  347. {
  348.     while (l1 < l2) {
  349.         *sp++ = *l1++;
  350.         if (sp >= &base[size])
  351.             len_error(ERROR);
  352.     }
  353.  
  354.     return sp;
  355. }
  356.  
  357. putmatch(which, buf, size)
  358. char    *buf;
  359. {
  360.     *(place(size, buf, buf, braslist[which - 1], braelist[which - 1])) = 0;
  361. }
  362.  
  363. /* Compile the string, that nextc knows about, into a sequence of
  364.    [TYPE][CHAR] where type says what kind of comparison to make
  365.    and CHAR is the character to compare with.  CHAR is actually
  366.    optional, like in the case of '.' there is no CHAR. */
  367.  
  368. compile(aeof, magic)
  369. {
  370.     register int    xeof,
  371.             c;
  372.     register char    *ep;
  373.     char    *lastep,
  374.         bracket[NBRA],
  375.         *bracketp,
  376.         **alt = alternates;
  377.     int    cclcnt;
  378.  
  379.     ep = expbuf;
  380.     *alt++ = ep;
  381.     xeof = aeof;
  382.     bracketp = bracket;
  383.  
  384.     nbra = 0;
  385.     lastep = 0;
  386.     for (;;) {
  387.         if (ep >= &expbuf[ESIZE])
  388.             REerror(toolong);
  389.         c = nextc();
  390.         if (c == xeof) {
  391.             if (bracketp != bracket)
  392.                 REerror(unmatched);
  393.             *ep++ = CEOF;
  394.             *alt = 0;
  395.             return;
  396.         }
  397.         if (c != '*')
  398.             lastep = ep;
  399.         if (!magic && index("*[.", c))
  400.             goto defchar;
  401.         switch (c) {
  402.         case '\\':
  403.             c = nextc();
  404.             if (!magic && index("()0123456789|wWbB", c))
  405.                 goto defchar;
  406.             switch (c) {
  407.             case 'w':
  408.                 *ep++ = CWORD;
  409.                 continue;
  410.  
  411.             case 'W':
  412.                 *ep++ = CNWORD;
  413.                 continue;
  414.  
  415.             case 'b':
  416.                 *ep++ = CBOUND;
  417.                 continue;
  418.  
  419.             case 'B':
  420.                 *ep++ = CNBOUND;
  421.                 continue;
  422.  
  423.             case '(':
  424.                 if (nbra >= NBRA)
  425.                     REerror(unmatched);
  426.                 *bracketp++ = nbra;
  427.                 *ep++ = CBRA;
  428.                 *ep++ = nbra++;
  429.                 continue;
  430.  
  431.             case ')':
  432.                 if (bracketp <= bracket)
  433.                     REerror(unmatched);
  434.                 *ep++ = CKET;
  435.                 *ep++ = *--bracketp;
  436.                 continue;
  437.             case '|':    /* Another alternative */
  438.                 if (alt >= &alternates[NALTS])
  439.                     REerror("Too many alternates");
  440.                 *ep++ = CEOF;
  441.                 *alt++ = ep;
  442.                 continue;
  443.  
  444.             case '1':
  445.             case '2':
  446.             case '3':
  447.             case '4':
  448.             case '5':
  449.                 *ep++ = CBACK;
  450.                 *ep++ = c - '1';
  451.                 continue;
  452.  
  453.             }
  454.             goto defchar;
  455.  
  456.         case '.':
  457.             *ep++ = CDOT;
  458.             continue;
  459.  
  460.         case '\n':
  461.             goto cerror;
  462.  
  463.         case '*':
  464.             if (lastep == 0 || *lastep == CBRA || *lastep == CKET)
  465.                 goto defchar;
  466.             *lastep |= STAR;
  467.             continue;
  468.  
  469.         case '^':
  470.             if (ep != expbuf && ep[-1] != CEOF)
  471.                 goto defchar;
  472.             *ep++ = CIRC;
  473.             continue;
  474.  
  475.         case '$':
  476.             if (((REpeekc = nextc()) != xeof) && REpeekc != '\\')
  477.                 goto defchar;
  478.             *ep++ = CDOL;
  479.             continue;
  480.  
  481.         case '[':
  482.             *ep++ = CCL;
  483.             *ep++ = 0;
  484.             cclcnt = 1;
  485.             if ((c = nextc()) == '^') {
  486.                 c = nextc();
  487.                 ep[-2] = NCCL;
  488.             }
  489.             do {
  490.                 if (c == '\\')
  491.                     c = nextc();
  492.                 if (c == '\n')
  493.                     goto cerror;
  494.                 if (c == xeof)
  495.                     REerror("Missing ']'");
  496.                 *ep++ = c;
  497.                 cclcnt++;
  498.                 if (ep >= &expbuf[ESIZE])
  499.                     REerror(toolong);
  500.             } while ((c = nextc()) != ']');
  501.             lastep[1] = cclcnt;
  502.             continue;
  503.  
  504.         defchar:
  505.         default:
  506.             *ep++ = CCHR;
  507.             *ep++ = c;
  508.         }
  509.     }
  510.    cerror:
  511.     expbuf[0] = 0;
  512.     nbra = 0;
  513.     REerror(syntax);
  514. }
  515.  
  516. /* Look for a match in `line' starting at `fromchar' from the beginning */
  517.  
  518. execute(fromchar, line)
  519. LINE    *line;
  520. {
  521.     register char    *p1,
  522.             c;
  523.  
  524.     for (c = 0; c < NBRA; c++) {
  525.         braslist[c] = 0;
  526.         braelist[c] = 0;
  527.     }
  528.     ignore(getright(line, genbuf));
  529.     locs = p1 = genbuf + fromchar;
  530.  
  531.     if (dir < 0)
  532.         locs = genbuf;
  533.  
  534.     /* fast check for first character */
  535.  
  536.     if (expbuf[0] == CCHR && !alternates[1]) {
  537.         c = expbuf[1];
  538.         do {
  539.             if (!CharCom(*p1, c))
  540.                 continue;
  541.             if (advance(p1, expbuf)) {
  542.                 loc1 = p1;
  543.                 return 1;
  544.             }
  545.         } while (dir > 0 ? *p1++ : p1-- > genbuf);
  546.         return 0;
  547.     }
  548.     /* regular algorithm */
  549.     do {
  550.         register char    **alt = alternates;
  551.  
  552.         while (*alt)
  553.             if (advance(p1, *alt++)) {
  554.                 loc1 = p1;
  555.                 return 1;
  556.             }
  557.     } while (dir > 0 ? *p1++ : p1-- > genbuf);
  558.  
  559.     return 0;
  560. }
  561.  
  562. /* Does the actual comparison, lp is the buffer line and ep is the
  563.    expression pointer.  Returns 1 if it found a match or 0 if it
  564.    didn't. */
  565.  
  566. advance(lp, ep)
  567. register char    *ep,
  568.         *lp;
  569. {
  570.     register char    *curlp;
  571.     int    i;
  572.  
  573.     for (;;) switch (*ep++) {
  574.  
  575.     case CIRC:    /* If we are not at the beginning
  576.                of the line there isn't a
  577.                match. */
  578.  
  579.         if (lp == genbuf)
  580.             continue;
  581.         return 0;
  582.  
  583.     case CCHR:    /* Normal comparison, if they're the same, continue */
  584.         if (CharCom(*ep++, *lp++))
  585.             continue;
  586.         return 0;
  587.  
  588.     case CDOT:    /* Any character matches.  Can only fail if we are
  589.                at the end of the buffer line already */
  590.         if (*lp++)
  591.             continue;
  592.         return 0;
  593.  
  594.     case CDOL:    /* Only works if we are at the end of the line */
  595.         if (*lp == 0)
  596.             continue;
  597.         return 0;
  598.  
  599.     case CEOF:    /* If we get here then we made it! */
  600.         loc2 = lp;
  601.         return 1;
  602.  
  603.     case CWORD:    /* Is this a word character? */
  604.         if (*lp && isword(*lp)) {
  605.             lp++;
  606.             continue;
  607.         }
  608.         return 0;
  609.  
  610.     case CNWORD:    /* Is this NOT a word character */
  611.         if (*lp && !isword(*lp)) {
  612.             lp++;
  613.             continue;
  614.         }
  615.         return 0;
  616.  
  617.     case CBOUND:    /* Is this at a word boundery */
  618.         if (    (*lp == 0) ||        /* end of line */
  619.             (lp == genbuf) ||    /* Beginning of line */
  620.             (isword(*lp) != isword(*(lp - 1)))    )
  621.                     /* Characters are of different
  622.                        type i.e one is part of a
  623.                        word and the other isn't. */
  624.             continue;
  625.         return 0;
  626.  
  627.     case CNBOUND:    /* Is this NOT a word boundery */
  628.         if (    (*lp) &&    /* Not end of the line */
  629.             (isword(*lp) == isword(*(lp - 1)))    )
  630.             continue;
  631.         return 0;
  632.  
  633.     case CCL:    /* Is this a member of [] */
  634.         if (cclass(ep, *lp++, 1)) {
  635.             ep += *ep;
  636.             continue;
  637.         }
  638.         return 0;
  639.  
  640.     case NCCL:    /* Is this NOT a member of [] */
  641.         if (cclass(ep, *lp++, 0)) {
  642.             ep += *ep;
  643.             continue;
  644.         }
  645.         return 0;
  646.  
  647.     case CBRA:
  648.         braslist[*ep++] = lp;
  649.         continue;
  650.  
  651.     case CKET:
  652.         braelist[*ep++] = lp;
  653.         continue;
  654.  
  655.     case CBACK:
  656.         if (braelist[i = *ep++] == 0)
  657.             goto badcase;
  658.         if (backref(i, lp)) {
  659.             lp += braelist[i] - braslist[i];
  660.             continue;
  661.         }
  662.         return 0;
  663.  
  664.     case CWORD | STAR:    /* Any number of word characters */
  665.         curlp = lp;
  666.         while (*lp++ && isword(*(lp - 1)))
  667.             ;
  668.         goto star;
  669.  
  670.     case CNWORD | STAR:
  671.         curlp = lp;
  672.         while (*lp++ && !isword(*(lp - 1)))
  673.             ;
  674.         goto star;
  675.  
  676.     case CBACK | STAR:
  677.         curlp = lp;
  678.         while (backref(i, lp))
  679.             lp += braelist[i] - braslist[i];
  680.         while (lp >= curlp) {
  681.             if (advance(lp, ep))
  682.                 return 1;
  683.             lp -= braelist[i] - braslist[i];
  684.         }
  685.         continue;
  686.  
  687.     case CDOT | STAR:    /* Any number of any character */
  688.         curlp = lp;
  689.         while (*lp++)
  690.             ;
  691.         goto star;
  692.  
  693.     case CCHR | STAR:    /* Any number of the current character */
  694.         curlp = lp;
  695.         while (CharCom(*lp++, *ep))
  696.             ;
  697.         ep++;
  698.         goto star;
  699.  
  700.     case CCL | STAR:
  701.     case NCCL | STAR:
  702.         curlp = lp;
  703.         while (cclass(ep, *lp++, ep[-1] == (CCL | STAR)))
  704.             ;
  705.         ep += *ep;
  706.         goto star;
  707.  
  708.     star:
  709.         do {
  710.             lp--;
  711.             if (lp < locs)
  712.                 break;
  713.             if (advance(lp, ep))
  714.                 return 1;
  715.         } while (lp > curlp);
  716.         return 0;
  717.  
  718.     default:
  719. badcase:
  720.         REerror("advance");
  721.     }
  722.     /* NOTREACHED */
  723. }
  724.  
  725. backref(i, lp)
  726. register int    i;
  727. register char    *lp;
  728. {
  729.     register char    *bp;
  730.  
  731.     bp = braslist[i];
  732.     while (*bp++ == *lp++)
  733.         if (bp >= braelist[i])
  734.             return 1;
  735.     return 0;
  736. }
  737.  
  738. cclass(set, c, af)
  739. register char    *set,
  740.         c;
  741. {
  742.     register int    n;
  743.     char    *base;
  744.  
  745.     if (c == 0)
  746.         return 0;
  747.     n = *set++;
  748.     base = set;
  749.     while (--n) {
  750.         if (*set == '-' && set > base) {
  751.             if (c >= *(set - 1) && c <= *(set + 1))
  752.                 return af;
  753.         } else if (*set++ == c)
  754.             return af;
  755.     }
  756.     return !af;
  757. }
  758.  
  759. /* end */
  760.